43  数据结构之字典

43.1 引言字典的键值对与哈希表

理论背景:哈希表的实现原理

Python字典(Dict)是基于哈希表(Hash Table)实现的关联数据结构。从计算机科学的角度来看,字典是抽象数据类型(Abstract Data Type)Map的一种高效实现:

  1. 键值对映射(Key-Value Mapping): 每个键(Key)唯一对应一个值(Value)
  2. 哈希函数(Hash Function): hash(key) → 整数索引,将键转换为数组索引
  3. 冲突解决(Collision Resolution): 处理多个键映射到同一索引的情况

数学分析:哈希函数的设计

理想哈希函数应该满足: \[ \forall key_1 \neq key_2: hash(key_1) \neq hash(key_2) \]

但实际上,由于键空间远大于数组大小,冲突不可避免。Python使用以下策略:

  1. 开放寻址法(Open Addressing): 当发生冲突时,寻找下一个空闲槽位
  2. 探测序列(Probe Sequence): \(h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m\) 其中\(i\)是探测次数,\(h_1\)和\(h_2\)是两个哈希函数

时间复杂度分析:

操作 平均情况 最坏情况 说明
插入 O(1) O(n) 负载因子< 0.66时
查找 O(1) O(n) 同上
删除 O(1) O(n) 同上

Python字典保持负载因子(Load Factor)低于2/3,确保平均性能为O(1)。

字典的四大核心特性:

特性 技术实现 时间复杂度 金融应用场景
键唯一性 哈希表约束 - 股票代码映射
快速查找 哈希计算 O(1)平均 实时行情查询
有序性(Python 3.7+) 维护插入顺序 O(1) 时间序列索引
异构性 键值可变类型 - 多维度数据

补充说明:为什么字典查找比列表快100倍?

假设有1000只股票: - 列表查找: 平均需要500次比较(O(n)) - 字典查找: 只需1次哈希计算(O(1))

性能差异: 500倍!这正是高频交易系统使用字典存储订单簿的原因。

易混淆概念辨析:Python 3.6 vs 3.7的字典有序性

  • Python 3.6: 字典有序是实现细节(CPython的副作用)
  • Python 3.7+: 字典有序成为语言规范(官方保证)

因此,在Python 3.7+中,可以放心依赖字典的插入顺序。

43.2 字典的创建

平台任务解答代码

以下代码与教学平台任务要求完全一致：

列表 43.1 
# 注：该代码块包含未完成的填空代码，需要在平台上完成
# ⚠️ 平台原始代码 - 请原样输入至教学平台（注释除外），平台才会判定答案正确
#任务一
dict1 = {"汇率变量":"美元兑人民币","日期":"2024-08-30","中间价":"7.1124","涨跌幅":"-0.0025"}  
dict2 = {"汇率变量":"欧元兑人民币","日期":"2024-08-21","中间价":"7.9325","涨跌幅":"0.0038"}  # 定义字典dict2
dict3 = {"汇率变量":"港元兑人民币","日期":"2024-08-19","中间价":"0.9162","涨跌幅":"-0.0003"}  # 定义字典dict3
dict4 = {"汇率变量":"英镑兑人民币","日期":"2024-08-08","中间价":"9.0701","涨跌幅":"0.0011"}  # 定义字典dict4

print(dict1.keys()) #输出字典dict1的全部键码

print(dict2.values()) #输出字典dict2的全部数值

print(dict3.items())  #输出字典dict3的全部元素


#任务二
dict1 = {"汇率变量":"美元兑人民币","日期":"2024-08-30","中间价":"7.1124","涨跌幅":"-0.0025"}  
dict2 = {"汇率变量":"欧元兑人民币","日期":"2024-08-21","中间价":"7.9325","涨跌幅":"0.0038"}  # 定义字典dict2
dict4 = {"汇率变量":"英镑兑人民币","日期":"2024-08-08","中间价":"9.0701","涨跌幅":"0.0011"}  # 定义字典dict4
 
print(dict1["日期"])   #查询美元兑人民币汇率的具体日期
 
print(dict2["中间价"])  #查询欧元兑人民币汇率的中间价
 
print(dict4["涨跌幅"])   #查询英镑兑人民币的涨跌幅
 
#任务三
dict2 = {"汇率变量":"欧元兑人民币","日期":"2024-08-21","中间价":"7.9325","涨跌幅":"0.0038"}
 
dict2["日期"] = "2024-08-29"           #修改字典2新的日期

dict2["中间价"] = 7.9318               #修改字典2新的中间价

dict2["涨跌幅"] = -0.0037              #修改字典2新的涨跌幅

print(dict2)  # 输出变量dict2的值

#任务四
dict3 = {"汇率变量":"港元兑人民币","日期":"2024-08-19","中间价":"0.9162","涨跌幅":"-0.0003"}

#使用update函数在dict3中添加"前一日中间价":"0.9165","前一日涨跌幅":"0.0002"
dict3.update({"前一日中间价":"0.9165","前一日涨跌幅":"0.0002"})   
print(dict3)  # 输出任务四
 
dict4 = {"汇率变量":"英镑兑人民币","日期":"2024-08-08","中间价":"9.0701","涨跌幅":"0.0011"}  # 定义字典dict4
del dict4["涨跌幅"]           #删除dict4的涨跌幅
print(dict4)  # 输出变量dict4的值
列表 43.2 
# 方式1:字面量语法(推荐)
# 花括号{}是字典的字面量语法
# 键值对格式: 键:值,使用冒号分隔
stock_codes_a = {
    '600': '上证A股',
    '900': '上证B股',
    '000': '深证A股',
    '200': '深证B股',
    '400': '三板市场股票'
}

# 方式2:dict()构造函数
# 先创建空字典,然后逐个添加键值对
stock_codes_b = dict()  # 创建空字典
stock_codes_b['600'] = '上证A股'  # 添加键值对
stock_codes_b['900'] = '上证B股'
stock_codes_b['000'] = '深证A股'
stock_codes_b['200'] = '深证B股'
stock_codes_b['400'] = '三板市场股票'

# 方式3:dict.fromkeys()批量创建
# 适用于创建所有值相同的字典
codes = ['600', '900', '000']  # 键列表
default_value = '其他'  # 默认值
stock_codes_c = dict.fromkeys(codes, default_value)

# 打印字典内容
# 字典的字符串表示格式为 {键: 值, ...}
print('字典A:', stock_codes_a)

# 通过键访问值
# stock_codes_a['000']获取键'000'对应的值
print(f"\n'000'对应: {stock_codes_a['000']}")  # 输出: 深证A股

代码深度解析:

  1. 字典的内存结构:

    # CPython 3.8+的字典使用紧凑表(Compact Table)
# 每个条目占用24字节:
# - 哈希值: 8字节
# - 键指针: 8字节
# - 值指针: 8字节

# 对于5个键值对的字典:
# 内存占用 ≈ 5 × 24 = 120字节 + 开销

  2. 哈希冲突的实际影响:

    # 演示哈希冲突
# 假设两个不同的键产生相同的哈希值(简化示例)

dict1 = {}
dict1['apple'] = 1
# 假设'banana'的哈希值与'apple'冲突
dict1['banana'] = 2  # Python会自动处理冲突

# 对用户透明,无需关心内部实现
print(dict1)  # {'apple': 1, 'banana': 2}

  3. 创建方式的性能对比:

    import time

# 方式1:字面量(最快)
start = time.time()
for _ in range(100000):
    d = {'a': 1, 'b': 2, 'c': 3}
print(f'字面量: {time.time() - start:.4f}秒')

# 方式2:dict()构造函数
start = time.time()
for _ in range(100000):
    d = dict(a=1, b=2, c=3)
print(f'dict(): {time.time() - start:.4f}秒')

  4. 金融应用:股票代码分类:

    # 中国股票代码规则:
# - 600xxx, 601xxx, 603xxx: 上交所主板
# - 300xxx: 深交所创业板
# - 688xxx: 上交所科创板

code_classification = {
    '600': '上交所主板',
    '601': '上交所主板',
    '603': '上交所主板',
    '300': '创业板',
    '688': '科创板'
}

# 查询股票类别
def classify_stock(code):
    prefix = code[:3]  # 获取前3位
    return code_classification.get(prefix, '未知类别')

print(classify_stock('600519'))  # 上交所主板
print(classify_stock('300750'))  # 创业板

43.3 字典的操作

列表 43.3 
# 创建股票代码到名称的映射
# 键是股票代码(字符串),值是股票名称(字符串)
stock_dict = {
    '600519.SH': '贵州茅台',
    '000858.SZ': '五粮液',
    '600036.SH': '招商银行'
}

# 访问元素:使用get()方法(推荐)
# get()方法在键不存在时返回默认值,不会报错
# 语法: dict.get(key, default_value)
print('查询600519.SH:', stock_dict.get('600519.SH', '未知'))
# 输出: 贵州茅台

# 查询不存在的键
print('查询999999.XX:', stock_dict.get('999999.XX', '未知'))
# 输出: 未知 (如果用stock_dict['999999.XX']会报KeyError)

# 添加新键值对
# 如果键已存在,会覆盖原值
stock_dict['601318.SH'] = '中国平安'

# 删除键值对
# del语句会从字典中移除键,如果键不存在会报KeyError
del stock_dict['600036.SH']  # 删除'招商银行'

# 获取所有键
# keys()返回dict_keys对象,需要转换为列表查看
print(f'\n键: {list(stock_dict.keys())}')
# 输出: ['600519.SH', '000858.SZ', '601318.SH']

# 获取所有值
# values()返回dict_values对象
print(f'值: {list(stock_dict.values())}')
# 输出: ['贵州茅台', '五粮液', '中国平安']

# 获取字典大小
# len()函数返回键值对的数量
print(f'项数: {len(stock_dict)}')  # 输出: 3

代码深度解析:

  1. 访问方式的对比:

    # 方式1:直接访问(键不存在时报错)
try:
    name = stock_dict['999999.XX']
except KeyError:
    print('键不存在!')
    name = None

# 方式2:get()方法(键不存在时返回默认值)
name = stock_dict.get('999999.XX', None)

# 方式2更安全,推荐使用

  2. 删除操作的安全性:

    # 方法1:del语句(键不存在时报错)
# del stock_dict['999999.XX']  # KeyError!

# 方法2:pop()方法(键不存在时返回默认值)
removed = stock_dict.pop('999999.XX', None)
print(removed)  # None (不会报错)

# 方法3:popitem()删除并返回最后一个键值对
# Python 3.7+中,字典保持插入顺序
key, value = stock_dict.popitem()
print(f'删除了: {key} -> {value}')

  3. 字典更新操作:

    # update()方法:批量更新字典
new_stocks = {
    '000001.SZ': '平安银行',
    '601318.SH': '中国平安(更新)'
}
stock_dict.update(new_stocks)
# 如果键已存在,会更新值
# 如果键不存在,会添加新键值对

  4. 金融应用:实时行情更新:

    # 模拟实时行情更新
quotes = {
    '600519.SH': 1850.00,
    '000858.SZ': 220.50
}

# 更新价格
def update_price(code, new_price):
    if code in quotes:  # 检查键是否存在
        old_price = quotes[code]
        quotes[code] = new_price
        change = (new_price - old_price) / old_price
        print(f'{code} 更新: {old_price:.2f} -> {new_price:.2f} ({change:+.2%})')
    else:
        quotes[code] = new_price
        print(f'{code} 新增: {new_price:.2f}')

update_price('600519.SH', 1860.00)  # 更新
update_price('000001.SZ', 18.50)    # 新增

43.4 字典的遍历

列表 43.4 
# 创建股票价格字典
# 键是股票名称,值是股票价格
prices = {'贵州茅台': 1850, '五粮液': 220, '招商银行': 45}

# 方式1:遍历键
# for key in dict: 等价于 for key in dict.keys():
print('遍历键:')
for key in prices:
    print(f'  {key}')
# 输出:
#   贵州茅台
#   五粮液
#   招商银行

# 方式2:遍历键值对
# items()方法返回(键, 值)元组的迭代器
print('\n遍历键值对:')
for key, value in prices.items():
    # 同时解包键和值
    print(f'  {key}: {value}元')
# 输出:
#   贵州茅台: 1850元
#   五粮液: 220元
#   招商银行: 45元

# 方式3:遍历值
# values()方法返回值的迭代器
print('\n遍历值:')
for value in prices.values():
    print(f'  {value}元')

# 字典推导式:创建新字典的优雅方式
# 语法: {键表达式: 值表达式 for item in iterable}
# 下面的代码将字典的键值对反转
inverted = {v: k for k, v in prices.items()}
print(f'\n反转字典: {inverted}')
# 输出: {1850: '贵州茅台', 220: '五粮液', 45: '招商银行'}

# 注意:如果原字典的值不唯一,反转会丢失数据!
# 因为字典的键必须唯一

代码深度解析:

  1. 遍历方式的性能对比:

    import time

large_dict = {i: i**2 for i in range(1000000)}

# 方式1:遍历键
start = time.time()
for key in large_dict:
    _ = large_dict[key]
print(f'遍历键: {time.time() - start:.4f}秒')

# 方式2:遍历键值对
start = time.time()
for key, value in large_dict.items():
    _
print(f'遍历键值对: {time.time() - start:.4f}秒')

# 方式2稍快,因为避免了额外的哈希查找

  2. 字典推导式的应用:

    # 应用1:过滤字典
# 找出价格大于100的股票
expensive = {k: v for k, v in prices.items() if v > 100}
print(expensive)  # {'贵州茅台': 1850, '五粮液': 220}

# 应用2:转换字典值
# 将价格转换为万元
prices_wan = {k: v/10000 for k, v in prices.items()}
print(prices_wan)
# {'贵州茅台': 0.185, '五粮液': 0.022, '招商银行': 0.0045}

# 应用3:合并两个字典
dict1 = {'a': 1, 'b': 2}
dict2 = {'c': 3, 'd': 4}
merged = {**dict1, **dict2}  # Python 3.5+的解包语法
print(merged)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}

  3. 金融应用:计算投资组合权重:

    # 持仓价值
holdings = {
    '贵州茅台': 185000,
    '五粮液': 44000,
    '招商银行': 22500
}

total = sum(holdings.values())

# 计算权重
weights = {stock: value/total for stock, value in holdings.items()}

print('持仓权重:')
for stock, weight in sorted(weights.items(), key=lambda x: -x[1]):
    print(f'  {stock}: {weight:.2%}')

  4. 内存视图:字典的内部结构:

    # 查看字典的内存占用
import sys

small_dict = {'a': 1, 'b': 2}
print(f'字典大小: {sys.getsizeof(small_dict)}字节')

# 字典包含多个部分:
# - 哈希表(主要部分)
# - 条目数组(存储键值对)
# - 元数据(大小、版本等)

43.5 金融应用股票代码映射

列表 43.5 
# 股票代码到名称的映射
# 这是一个典型的"查找表"(Lookup Table)应用场景
# 字典的O(1)查找性能使得它非常适合此类应用
code_to_name = {
    '600519.SH': '贵州茅台',
    '000858.SZ': '五粮液',
    '600036.SH': '招商银行',
    '601318.SH': '中国平安',
    '000001.SZ': '平安银行'
}

# 批量查询的股票代码列表
codes_to_query = ['600519.SH', '000858.SZ', '000001.SZ']

# 遍历并查询
print('股票查询结果:')
for code in codes_to_query:
    # 使用get()方法,如果代码不存在返回'未知股票'
    # 这避免了KeyError异常
    name = code_to_name.get(code, '未知股票')
    print(f'{code}: {name}')

# 反向映射:从名称到代码
# 使用字典推导式交换键和值
# 注意:如果名称不唯一,会丢失数据!
name_to_code = {v: k for k, v in code_to_name.items()}

# 查询平安银行的代码
# 使用get()方法,如果名称不存在返回None
print(f'\n平安银行代码: {name_to_code.get("平安银行")}')
# 输出: 000001.SZ

# 查询不存在的名称
print(f'腾讯代码: {name_to_code.get("腾讯")}')
# 输出: None (不会报错)

代码深度解析:

  1. 双向映射的设计模式:

    # 更健壮的双向映射实现
class BidirectionalMap:
    def __init__(self):
        self.key_to_value = {}
        self.value_to_key = {}

    def add(self, key, value):
        # 检查值是否已存在
        if value in self.value_to_key:
            raise ValueError(f'值{value}已存在!')

        self.key_to_value[key] = value
        self.value_to_key[value] = key

    def get_key(self, value):
        return self.value_to_key.get(value)

    def get_value(self, key):
        return self.key_to_value.get(key)

# 使用示例
bm = BidirectionalMap()
bm.add('600519.SH', '贵州茅台')
print(bm.get_key('贵州茅台'))  # 600519.SH
print(bm.get_value('600519.SH'))  # 贵州茅台

  2. 默认字典的应用:

    from collections import defaultdict

# 使用defaultdict避免手动检查键是否存在
# 当访问不存在的键时,自动创建默认值
counter = defaultdict(int)  # 默认值为0

# 统计股票出现次数
codes = ['600519.SH', '000858.SZ', '600519.SH', '600519.SH']
for code in codes:
    counter[code] += 1  # 即使code不存在,也不会报错

print(counter)  # defaultdict(<class 'int'>, {'600519.SH': 3, '000858.SZ': 1})

  3. 嵌套字典的应用:

    # 存储股票的多维度信息
stock_info = {
    '600519.SH': {
        'name': '贵州茅台',
        'price': 1850.00,
        'pe': 45.2,
        'market_cap': 2325000000000  # 市值(元)
    },
    '000858.SZ': {
        'name': '五粮液',
        'price': 220.50,
        'pe': 32.8,
        'market_cap': 856000000000
    }
}

# 访问嵌套信息
maotai = stock_info['600519.SH']
print(f'{maotai["name"]}: PE={maotai["pe"]}, 市值={maotai["market_cap"]/1e8:.0f}亿元')

  4. OrderedDict的应用:

    from collections import OrderedDict

# OrderedDict在Python 3.7+之前很有用
# 在Python 3.7+中,普通dict已经有序

# 维护时间序列数据
time_series = OrderedDict()
time_series['2024-01-01'] = 1850.0
time_series['2024-01-02'] = 1860.5
time_series['2024-01-03'] = 1855.0

# 获取最近的价格
latest_date = next(reversed(time_series))
latest_price = time_series[latest_date]
print(f'最新价格({latest_date}): {latest_price}')

性能优化技巧:

  1. 预分配字典大小(如果可能):

    # 对于已知大小的字典,预分配可以提高性能
d = {}
d.update({i: i**2 for i in range(1000)})
# 比逐个插入更快

  2. 使用__slots__减少内存:

    class Stock:
    __slots__ = ['code', 'name', 'price']
    def __init__(self, code, name, price):
        self.code = code
        self.name = name
        self.price = price

# 使用对象而非字典可以减少内存占用

  3. 避免频繁的字典操作:

    # 不推荐
for stock in stocks:
    if stock['code'] not in cache:
        cache[stock['code']] = {}
    cache[stock['code']]['price'] = stock['price']

# 推荐
for stock in stocks:
    if stock['code'] in cache:
        cache[stock['code']]['price'] = stock['price']
    else:
        cache[stock['code']] = {'price': stock['price']}

最佳实践总结:

  1. 使用字典的场景:

    • 需要通过键快速查找值
    • 键是字符串或数字等不可变类型
    • 需要维护键值对关系
    • 数据需要频繁查询

  2. 避免字典的场景:

    • 需要保持顺序(Python 3.6-)
    • 需要序列化(考虑使用OrderedDict)
    • 键是可变类型(如列表)

  3. 字典vs列表的选择决策树:

    需要通过特定标识符查找数据?
├─ 是 → 使用字典
└─ 否 → 需要按顺序访问?
    ├─ 是 → 使用列表
    └─ 否 → 使用集合(去重)